#coding: utf-8
'''
Created on 29/05/2013

@author: Vagner Clementino
Código fonte da questão 04 da lista 02 da disciplina Criptografia
'''

from primeGen import miller_rabin
import random
import fractions

def rsa_factor(n,a,b):
    '''
        Método que retorna um fator primo de n encontrando uma raiz quadrada
        trivial de 1 módulo n. Com entrada o algoritmo recebe as chaves públicas
        do RSA (n,b) e ainda a chave privada a (expoente de encripitação). O
        algoritmo assumo que ab = 1 mod ((p-1) (q-1)) e n = p.q
        O algoritmo retorna o fator de n ou -1 quando não for possivel
        determiná-lo
    '''
    #Escrevendo ab-1 = 2 ^s * r, onde r é impar
    
    tupla_rs = miller_rabin.get_rs(a * b)
    r = long(tupla_rs[0])
    s = tupla_rs[1]
    
    #Escolhendo aleatóriamente um w entre 1 e (n-1)
    w = random.randint(1, (n-1))
    #w = 9983
    #w = 13461
    
    x = fractions.gcd(w, n)
    
    if x > 1 and x < n:
        #X é fator de n
        return x
    v = miller_rabin.exp_mod_n(w, r, n)
    if v % n == 1:
        #Erro: o algortimo falhou em encontrar o fator
        #devendo ser executado novamente
        return -1
    while v % n != 1:
        u = v
        v = miller_rabin.exp_mod_n(v, 2, n)
    if u % n == (n-1):
        #Erro: o algortimo falhou em encontrar o fator
        #devendo ser executado novamente
        return -1
    else:
        x = fractions.gcd(u + 1, n)
        # é fator de n
        return x
        
        
        
    